package test;

/**
 *create by tbj
 */
public class MyBinarySearchTree<Key extends Comparable<Key>,Value> {
	private Node root;
	private int count;
	private class Node{
		private Key key;
		private Value value;
		private Node left;
		private Node right;
		public Node(Key key,Value value){
			this.key=key;
			this.value=value;
			left=right=null;
		}
	}
	public MyBinarySearchTree(){
		root=null;
		count=0;
	}
	public int size(){
		return count;
	}
	public boolean isEmpty(){
		return count==0;
	}
	public void insert(Key key,Value value){
		root=_insert(root,key,value);
	}
	private Node _insert(Node node,Key key,Value value){
		if(node == null){
			count++;
			return new Node(key,value);
		}else if(key.compareTo(node.key) < 0){
			node.left=_insert(node.left, key, value);
		}else if(key.compareTo(node.key) > 0){
			node.right=_insert(node.right, key, value);
		}else{
			node.value=value;
		}
		return node;
	}
	public boolean contain(Key key){
		return _contain(root,key);
	}
	private boolean _contain(Node node,Key key){
		if(node == null){
			return false;
		}else if(key.compareTo(node.key) < 0){
			return _contain(node.left, key);
		}else if(key.compareTo(node.key) > 0){
			return _contain(node.right, key);
		}else{
			return true;
		}
	}
	public Value search(Key key){
		return _search(root,key);
	}
	private Value _search(Node node,Key key){
		if(node == null){
			return null;
		}else if(key.compareTo(node.key) == 0){
			return node.value;
		}else if(key.compareTo(node.key) < 0){
			return _search(node.left, key);
		}else{
			return _search(node.right, key);
		}
	}
}
